package com.leetcode.algorithm.y22.m08.w2;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/**
 * 90. 子集 II
 * 
 * https://leetcode.cn/problems/subsets-ii/
 * 
 * @author jie.deng
 *
 */
class Question0090Solution02 {

	public List<List<Integer>> subsetsWithDup(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> result = new ArrayList<>();
		Deque<Integer> path = new ArrayDeque<>();
		backtracking(nums, result, 0, path);
		return result;
	}

	private void backtracking(int[] nums, List<List<Integer>> result, int startIdx, Deque<Integer> path) {
		result.add(new ArrayList<>(path));
		for (int i = startIdx; i < nums.length; i++) {
			if (i > startIdx && nums[i] == nums[i - 1]) {
				// 剪枝，剪掉重复的子集
				continue;
			}
			path.offerLast(nums[i]);
			backtracking(nums, result, i + 1, path);
			path.pollLast();
		}
	}

}